/**
 * 左倾二叉树（最小堆实现）
 */
public class LeftistTree {
    /**
     * 树节点类
     */
    static class Node {
        int key;          // 节点值
        int npl;          // 零路径长度（Null Path Length）
        Node left;        // 左子节点
        Node right;       // 右子节点

        public Node(int key) {
            this.key = key;
            this.npl = 0;  // 新节点的npl初始为0
            this.left = null;
            this.right = null;
        }
    }

    private Node root;    // 树根节点

    public LeftistTree() {
        root = null;
    }

    /**
     * 判断堆是否为空
     */
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * 合并两棵左倾树（核心操作）
     */
    public Node merge(Node x, Node y) {
        if (x == null) return y;
        if (y == null) return x;

        // 确保x是较小根节点（最小堆性质）
        if (x.key > y.key) {
            Node temp = x;
            x = y;
            y = temp;
        }

        // 递归合并x的右子树和y
        x.right = merge(x.right, y);

        // 维护左倾性质：确保左子树的npl >= 右子树的npl
        if (x.left == null || x.left.npl < x.right.npl) {
            Node temp = x.left;
            x.left = x.right;
            x.right = temp;
        }

        // 更新npl值
        x.npl = (x.right == null) ? 0 : x.right.npl + 1;
        
        return x;
    }

    /**
     * 插入新元素
     */
    public void insert(int key) {
        root = merge(root, new Node(key));
    }

    /**
     * 删除并返回最小值
     */
    public int deleteMin() {
        if (isEmpty()) throw new IllegalStateException("Heap is empty");
        
        int minValue = root.key;
        root = merge(root.left, root.right);
        return minValue;
    }

    /**
     * 获取最小值（不删除）
     */
    public int findMin() {
        if (isEmpty()) throw new IllegalStateException("Heap is empty");
        return root.key;
    }

    /**
     * 合并另一棵左倾树
     */
    public void merge(LeftistTree other) {
        if (this == other) return; // 防止自合并
        root = merge(this.root, other.root);
        other.root = null; // 清空被合并的树
    }

    // 测试用例
    public static void main(String[] args) {
        LeftistTree heap1 = new LeftistTree();
        LeftistTree heap2 = new LeftistTree();

        // 向堆1插入数据
        heap1.insert(3);
        heap1.insert(8);
        heap1.insert(5);
        
        // 向堆2插入数据
        heap2.insert(4);
        heap2.insert(1);
        heap2.insert(7);

        // 合并两个堆
        heap1.merge(heap2);
        
        // 依次弹出最小值（应有序输出）
        System.out.println("Extracted values:");
        while (!heap1.isEmpty()) {
            System.out.print(heap1.deleteMin() + " ");  // 输出: 1 3 4 5 7 8
        }
    }
}